Increasing use of personal computers as word processors has brought an increased need for providing a plurality of font types for use with printers especially in conjunction with word processing programs. A "font," as used herein, refers to a group of characters having particular distinguishing configuration properties. Several fonts which are currently in use include Courier, Letter Gothic, Presentation, Times Roman, etc.
A common method of providing digital characterization of font characters is to provide a bit map representation for each character of the font. A bit map representation is a map of the character into a plurality of bit positions arranged in lines and columns, wherein each bit position represents a binary data bit. Typically, bit maps have whole bytes of columns, i.e., columns having 8 bits, 16 bits, 24 bits, etc. Association of a bit position with a zero indicates no character portion in that bit position of the map. Conversely, association of a bit position with a "1" indicates the existence of a portion of the character in that bit position of the map. Accordingly, printing in all bit positions of the map that are associated with a "1" will reproduce the character defined by the bit map. Mapping a character in this fashion may be accomplished using several conventions. As an example, and as used herein, the first line of the bit map represents the top of the character while the bottom line of the bit map represents the bottom of the character. Additionally, the first column of the bit map represents the left side of the character and the last column of the bit map represents the right side of the character. The data of a bit map that represents a single character is sometimes referred to as a "character block" of data.
Most personal computers and word processors that use font data include a printer for reproducing the characters of the font on a printed page. Printers that are particularly suited for reproducing bit map character data are referred to as "Scan line" printers. Scan line type printers are constructed to reproduce the first line of all bit mapped characters in a printed line, followed by the second line of all bit mapped characters in the printed line and continuing in this fashion until all characters in the printed line have been reproduced. Laser printers that are now commonly in use typically operate on a scan line basis. For these and other scan line type printers, font data may be permanently stored in the memory of cartridges that are mechanically and electrically coupled to the printer. The printer accesses the stored font data during a printing operation to receive the bit mapped data of the characters being printed. Since the font data is permanently stored in memory, the time necessary to compress the data is not critical. However, it is important to minimize the time necessary to decompress the data during printing. The amount of data storage available in a cartridge is limited and consequently the amount of font data that can be stored is limited.
In an effort to increase the number of varying fonts available to a particular user, without unnecessarily increasing the data storage requirements of the font data, it is desirable to provide a method for compressing the font data so that storage of the data requires a minimum amount of memory space. The compressed font data can then be decompressed before printing to insure accurate reproduction of the character.
Many compression and decompression techniques presently known rely upon recurring patterns in a data stream to enable efficient compression and later decompression of the data. Data encoding for facsimile transmission is one such example. Since most printed pages contain a small percentage of printing, the transmitted data typically include a series of data bits, the series having a large number of sequential zeros separated by smaller numbers of sequential ones. One method of compressing this data for transmission is to provide a binary-encoded number that identifies the number of zeros or ones in a sequence. Using this method, a sequence of 15 zeros can be encoded with just five data bits, as opposed to the 15 data bits required if the data is not encoded. However, this method of encoding is not efficient for data that has small numbers of sequential ones or zeros. Accordingly, the encoding sequence that is selected is dependent in large measure upon the nature of the data to be encoded.
Because many printers reproduce font data using "scan lines," it is desirable to store font data so that it can be reproduced on a line-by-line basis. For example, it is desirable to use a method for compressing font data wherein the first line of each character on a printed line can be decompressed and reproduced followed by the second line of each character, etc, until the last line of each character for that line is reproduced.
Further, since it is desirable to reduce the amount of time necessary to print a document, it is also desirable to reduce the amount of time necessary to decompress the compressed font data. However, it is noted in this regard that it is not necessary to reduce the amount of time necessary for compression of the font data. This is because the font data is compressed once and, thereafter, stored in memory. Subsequently, the data is only decompressed for printing. The compressed data remains stored in memory.